package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author Lzm
 * @version 1.0
 */
/*难点是去重*/
  /*这里用一个boolean数组来标志哪些元素正在被使用*/
  /*当boolean[i] = true时, 说明此时list中有这个nums[i]元素*/
  /*且当回溯后, 相应的boolean[i] 应该置为false*/
public class combinationSum2_ {
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new ArrayList<>();
  @Test
  public void combinationSum2Test(){
    int[] nums = new int[]{10,1,2,7,6,1,5};
    int target = 8;
    boolean[] used = new boolean[nums.length];
    Arrays.fill(used, false);
    backTracking(nums,target,0,used);
    System.out.println(result);
  }
  public void backTracking(int[] candidates, int target,int index,boolean[] used){
    if (sum(list) > target){
      return;
    }
      if (sum(list) == target){
        result.add(new LinkedList<>(list));
      }
      Arrays.sort(candidates);
      for(int i = index ; i < candidates.length ; i ++){
        if (sum(list) + candidates[i] > target) break;
        /*去重操作*/
        if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
        list.add(candidates[i]);
        used[i] = true;
        backTracking(candidates,target,i + 1,used);
        used[i] = false;
        list.removeLast();
      }
  }
  public static int sum(List<Integer> list){
    int sum = 0;
    for (Integer number : list) {
      sum += number;
    }
    return sum;
  }
}
